/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
        return NULL;
    if (head->next == NULL)
    {
        Node* newnode = (Node*)malloc(sizeof(Node));
        newnode->val = head->val;
        if (head->random != NULL)
        {
            newnode->random = newnode;
        }
        else
        {
            newnode->random = NULL;
        }
        newnode->next = NULL;
        return newnode;
    }
    Node* l1 = head;
    Node* l2 = head;
    while (l2 != NULL)
    {
        Node* newnode = (Node*)malloc(sizeof(Node));
        l2 = l2->next;
        newnode->val = l1->val;
        newnode->random = NULL;
        newnode->next = l2;
        l1->next = newnode;


        l1 = l2;
    }
    l1 = head;
    l2 = head;

    while (l2 != NULL)
    {
        l2 = l2->next;
        if (l1->random != NULL)
            l2->random = l1->random->next;
        else
            l2->random = NULL;
        l2 = l2->next;
        l1 = l2;
    }

    l1 = head;
    l2 = head;
    Node* newhead = l1->next;
    l2 = l2->next;
    while (l2 != NULL)
    {
        l1->next = l2->next;
        l1 = l2;
        l2 = l2->next->next;

        Node* tmp = l1;
        l1 = l1->next;
        tmp->next = l2;
        l1->next = l2->next;
        if (l2->next == NULL)
        {

            l2->next = NULL;
            l1->next = NULL;
            break;
        }


    }

    return newhead;
}